#include <stdio.h>
#include <stdlib.h>
#include <queue>

using namespace std;

/***
 * 把二叉树看做图 求二叉树中相距最远的两个节点间的距离
 * */
typedef int DataType;

typedef struct TNode
{
    DataType data;
    TNode *left, *right;
} * Tree, TNode;

// 最长距离为 树中所有子树的 左右子树最大深度之和 的最大值
// 返回值: 树的最大深度
// max: 树中结点距离的最大值
int GetTreeDeep(Tree T, int &max)
{
    if (T == NULL)
        return 0;

    int ldeep = GetTreeDeep(T->left, max);
    int rdeep = GetTreeDeep(T->right, max);
    max = ldeep + rdeep > max ? ldeep + rdeep : max;

    return ldeep > rdeep ? ldeep+1 : rdeep+1;
}


int GetDistance(Tree &T)
{
    if (T) {
        int max = 0;
        GetTreeDeep(T, max);
        return max;
    }
    return 0;
}

// 测试用
TNode *NewNode(int e)
{
    TNode *s = (TNode *)malloc(sizeof(TNode));
    s->data = e;
    s->left = NULL;
    s->right = NULL;
    return s;
}

// 层序遍历
void PrintTree(Tree T)
{
    queue<TNode *> q;
    if (T != NULL)
    {
        q.push(T);
    }
    while (!q.empty())
    {
        printf("%d ", q.front()->data);
        if (q.front()->left != NULL)
            q.push(q.front()->left);

        if (q.front()->right != NULL)
            q.push(q.front()->right);
        q.pop();
    }
}

int main()
{

    Tree T;
    T = NewNode(0);
    T->left = NewNode(1);
    T->right = NewNode(2);
    T->left->left = NewNode(3);
    T->left->right = NewNode(4);
    T->right->left = NewNode(5);
    //       0
    //    1     2
    //  3   4  5

    PrintTree(T);
    printf("\n");

    int e = GetDistance(T);
    printf("===>最大值: %d\n", e);
    return 0;
}